import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestPriorityQueue {
 //找出最小的K个数
 // 方式一：建立小根堆,再出k个元素
 public static void main1(String[] args) {
     int k=3;
     PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
     int[] arr={27,15,19,18,38};
     for (int i=0;i<arr.length;i++){
         priorityQueue.add(arr[i]);
     }
     for (int i=0;i<k;i++){
         int a=priorityQueue.poll();
         System.out.print(a+" ");
     }
 }
//方式二：建立大根堆，只包含k个元素
    static class Cmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1) ;
    }
}
    public static void main2(String[] args) {
     int k=3;
     Cmp cmp=new Cmp();
    PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(cmp);
    int[] arr={27,15,19,18,38};
    for (int i=0;i<k;i++){
        priorityQueue.add(arr[i]);
    }
    for (int j=k;j<arr.length;j++){
        int x=priorityQueue.peek();
        if(arr[j]<x){
            priorityQueue.poll();
            priorityQueue.add(arr[j]);
        }
    }
        System.out.println(priorityQueue);
    }
    //堆排序问题
    /*
    * 1.建立大根堆
    * 2.顶底元素和最后一个元素交换，再排序
    * 3.再取顶部元素
    */
    public static void main(String[] args) {
        Cmp cmp=new Cmp();
        int[] arr={27,15,19,18,28,34,65,49,25,37};
        for (int parent=(arr.length-1-1)/2;parent>=0;parent--){
            shifdown(arr,parent,arr.length);
        }//不能直接写称 PriorityQueue.add
        int end=arr.length-1;
        for (;end>0;end--){
            swap(arr,0,end);
            shifdown(arr,0,end);
        }
        System.out.println(Arrays.toString(arr));
    }
    //交换
    static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //向下调转
    static void shifdown(int[] arr,int parent,int len){
        int child=parent*2+1;
        while (child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child=child+1;
            }
            if(arr[parent]<arr[child]){
                swap(arr,parent,child);
                parent=child;
                child=2*parent+1;
            }else {break;}
        }
    }

}
